import java.util.*;

public class BinaryTreeUtil {
    //判断两棵树是否相同，以相同的方式遍历这两棵树
    public static boolean isSameTree(BinaryTree.BinaryTreeNode p, BinaryTree.BinaryTreeNode q) {
        //思路，如果两个结点的值不相等或者不同时为空，直接返回false
        if(p == null && q != null) {
            return false;
        }

        if(q == null && p != null) {
            return false;
        }

        if(p == null && q == null) {
            return true;
        }

        if(p.val != q.val) {
            return false;
        }
        //根节点相同，左子树相同并且右子树相同返回true
        return isSameTree(p.leftChild,q.leftChild) && isSameTree(p.rightChild,q.rightChild);
    }

    public static boolean isSubtree(BinaryTree.BinaryTreeNode root, BinaryTree.BinaryTreeNode subRoot) {
           //先判断根节点的值是否相同
           //先处理特殊情况
           if(root == null && subRoot == null) {
               return true;
           }

           if(root == null && subRoot != null) {
               return false;
           }

           if(root != null && subRoot == null) {
               return false;
           }

           if(root.val == subRoot.val) {
               //判断subroot是否是root和root的一颗子树是相同的
              if(isSameTree(root,subRoot)) {
                  return true;
              }
           }

           //判断subRoot是否是root左子树的子树或者是root右子树的子树
           return isSubtree(root.leftChild,subRoot) ||  isSubtree(root.rightChild,subRoot);
    }

    public static BinaryTree.BinaryTreeNode invertTree(BinaryTree.BinaryTreeNode root) {
        if(root == null) {
            return null;
        }

        //反转当前结点的左右子树
        BinaryTree.BinaryTreeNode tmp = root.leftChild;
        root.leftChild = root.rightChild;
        root.rightChild = tmp;

        //递归反转左子树
        invertTree(root.leftChild);
        //递归反转右子树
        invertTree(root.rightChild);
        //返回根节点
        return root;
    }

    public static boolean isBalance(BinaryTree.BinaryTreeNode root) {
          //处理特殊情况
        if(root == null) {
            return true;
        }

        //判断是否平衡
        if(Math.abs(BinaryTree.getHeight(root.leftChild) - BinaryTree.getHeight(root.rightChild)) > 1) {
            return false;
        }

        //判断左右子树是否都是平衡的
        return isBalance(root.leftChild) && isBalance(root.rightChild);
    }

    //判断是否对称
    private static boolean judgeSymmetric(BinaryTree.BinaryTreeNode left, BinaryTree.BinaryTreeNode right) {
        if(left == null && right == null) {
            return true;
        }

        if(left == null && right != null) {
            return false;
        }

        if(left != null && right == null) {
            return false;
        }

        if(left.val != right.val) {
            return false;
        }

        return judgeSymmetric(left.leftChild,right.rightChild) && judgeSymmetric(left.rightChild,right.leftChild);
    }

    //判断一颗二叉树是否对称
    public static boolean isSymmetric(BinaryTree.BinaryTreeNode root) {
        //我们认为空的二叉树是对称的
        if(root == null) {
            return true;
        }

        //只有一个结点的二叉树，再这道题中认为是对称的
        if(root.leftChild == null && root.rightChild == null) {
            return true;
        }

        //判断左右子树是否对称
        return judgeSymmetric(root.leftChild,root.rightChild);
    }

    public static List<List<Integer>> levelOrder(BinaryTree.BinaryTreeNode root) {
         //先写出传统的层序遍历
        LinkedList<BinaryTree.BinaryTreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();

        if(root == null) {
            return new ArrayList<>();
        }

        //将root入队
        queue.offer(root);
        while(!queue.isEmpty()) {
            ArrayList<Integer> curLow = new ArrayList<>();
            //出队
            int queueSize = queue.size();
            for(int i = 0;i < queueSize;i++) {

                BinaryTree.BinaryTreeNode curNode = queue.poll();
                curLow.add(curNode.val);
                //如果左孩子不为空，将左子树的根节点入队
                if(curNode.leftChild != null) {
                    queue.offer(curNode.leftChild);
                }
                //如果右孩子不为空，将右子树的根节点入队
                if(curNode.rightChild != null) {
                    queue.offer(curNode.rightChild);
                }
            }

            result.add(curLow);
            queueSize = queue.size();
        }
        return result;
    }

    //从下到上的层序遍历
    public static List<List<Integer>> levelOrderBottom(BinaryTree.BinaryTreeNode root) {
        //定义一个队列
        Queue<BinaryTree.BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        List<List<Integer>> result = new ArrayList<>();
        while(!queue.isEmpty()) {
            ArrayList<Integer> curRow = new ArrayList<>();
            int queueSize = queue.size();

            for (int i = 0; i < queueSize; i++) {
                BinaryTree.BinaryTreeNode curNode = queue.poll();

                curRow.add(curNode.val);

                if(curNode.leftChild != null) {
                    queue.offer(curNode.leftChild);
                }

                if(curNode.rightChild != null) {
                    queue.offer(curNode.rightChild);
                }
            }

            queueSize = queue.size();
            result.add(curRow);
        }

        Collections.reverse(result);
        return result;
    }


    //判断是不是一颗完全二叉树,这段代码还需要调试
    public static boolean isCompleteTree(BinaryTree.BinaryTreeNode root) {
         //建立一个队列
        LinkedList<BinaryTree.BinaryTreeNode> queue = new LinkedList<>();
        //处理root为空的情况
        if(root == null) {
            return true;
        }

        queue.offer(root);
        BinaryTree.BinaryTreeNode cur = queue.poll();
        while(cur != null) {
            queue.offer(cur.leftChild);
            queue.offer(cur.rightChild);
        }

        for (BinaryTree.BinaryTreeNode treeNode : queue) {
            if(treeNode != null) {
                return false;
            }
        }

        return true;

    }

    //递归写法
    public static BinaryTree.BinaryTreeNode lowestCommonAncestor(BinaryTree.BinaryTreeNode root, BinaryTree.BinaryTreeNode p, BinaryTree.BinaryTreeNode q) {
        //设置递归出口
        if(root == null) {
            return null;
        }

        if(root == p || root == q) {
            return root;
        }

        //记录左子树的搜寻结果
        BinaryTree.BinaryTreeNode left = lowestCommonAncestor(root.leftChild,p,q);
        //记录右子树的搜寻结果
        BinaryTree.BinaryTreeNode right = lowestCommonAncestor(root.rightChild,p,q);

        //如果left和right都不为空,说明p和q在root的两侧，此时root为p和q的公共祖先结点
        if(left != null && right != null) {
            return root;
        }

        //如果left为空但是right不为空，说明p或者q在root的右侧
        if(left == null && right != null) {
            return right;
        }

        //如果left不为空right为空，说明q或者q在root左侧
        if(left != null && right == null) {
            return left;
        }

        if(left == null && right == null) {
            return null;
        }
        return null;
    }

    public static int i = 0;

    //根据前序遍历序列和中序遍历序列来构造二叉树
    public static BinaryTree.BinaryTreeNode buildTreeByPreOrderandInOrder(int[] preOrder,int[] inOrder) {

        return buildTreeChildByPreOrderandInOrder(preOrder,inOrder,0, preOrder.length - 1);
    }

    //子方法，利用中序遍历序列来缩小查找前序的遍历序列的范围
    public static BinaryTree.BinaryTreeNode buildTreeChildByPreOrderandInOrder(int[] preOrder,int[] inOrder,int beginIndex,int overIndex) {
        //递归算法设置递归出口，现在还未知
        //当beginIndex > overIndex的时候返回null
        if(beginIndex > overIndex) {
            return null;
        }

        BinaryTree.BinaryTreeNode newNode = new BinaryTree.BinaryTreeNode(preOrder[i]);
        i++;

        int index = -1;

        //注意查找区间，避免出现相同元素
        for (int i = beginIndex; i <= overIndex; i++) {
             if(inOrder[i] == newNode.val) {
                 index = i;
             }
        }

        //递归构建左子树
        newNode.leftChild = buildTreeChildByPreOrderandInOrder(preOrder,inOrder,beginIndex,index - 1);
        //递归构建右子树
        newNode.rightChild = buildTreeChildByPreOrderandInOrder(preOrder,inOrder,index + 1,overIndex);
        return newNode;
    }

    public static int j;
    public static BinaryTree.BinaryTreeNode buildTreeByPostOrderAndInOrder(int[] postOrder,int[] inOrder) {
        j = postOrder.length - 1;
        return buildTreeChildByPostOrderAndInorder(postOrder,inOrder,0,postOrder.length - 1);
    }

    public static int getLength(int[] inOrder) {
        return inOrder.length;
    }

    public static BinaryTree.BinaryTreeNode buildTreeChildByPostOrderAndInorder(int[] postOrder,int[] inOrder,int beginIndex,int overIndex) {
        //递归出口
        if(beginIndex > overIndex) {
            return null;
        }

        //根据postOrder的最后一个元素来构造
        BinaryTree.BinaryTreeNode newNode = new BinaryTree.BinaryTreeNode(postOrder[j]);
        j--;

        int index = -1;
        //确认newNode在inOrder中的位置
        for (int k = beginIndex; k <= overIndex; k++) {
            if(inOrder[k] == newNode.val) {
                index = k;
            }
        }

        //递归构造右子树
        newNode.rightChild = buildTreeChildByPostOrderAndInorder(postOrder, inOrder, index + 1, overIndex);
        //递归构造左子树
        newNode.leftChild = buildTreeChildByPostOrderAndInorder(postOrder,inOrder,beginIndex,index - 1);

        //返回当前结点
        return newNode;
    }


//    public static void main(String[] args) {
//          BinaryTree tree = new BinaryTree();
//          tree.root = new BinaryTree.BinaryTreeNode(3);
//          tree.root.leftChild = new BinaryTree.BinaryTreeNode(9);
//          tree.root.rightChild = new BinaryTree.BinaryTreeNode(20);
//          tree.root.rightChild.leftChild = new BinaryTree.BinaryTreeNode(15);
//          tree.root.rightChild.rightChild = new BinaryTree.BinaryTreeNode(7);
//
//          List<List<Integer>> result = levelOrderBottom(tree.root);
//          String str = result.toString();
//          System.out.println(str);
//    }

    public static void main(String[] args) {
          BinaryTree tree = new BinaryTree();
          tree.root = new BinaryTree.BinaryTreeNode(3);
          tree.root.leftChild = new BinaryTree.BinaryTreeNode(9);
          tree.root.rightChild = new BinaryTree.BinaryTreeNode(20);
          tree.root.rightChild.leftChild = new BinaryTree.BinaryTreeNode(15);
          tree.root.rightChild.rightChild = new BinaryTree.BinaryTreeNode(7);

          List<List<Integer>> result = levelOrder(tree.root);
        System.out.println(result.toString());
    }
}
